﻿#pragma once
#include<vector>
using namespace std;
#include<iostream>


//template<class K, class V, class Hash = HashFunc<K>> 定义了一个模板类，其中 class Hash 是一个模板参数，并且它有一个默认值 HashFunc<K>。下面详细分析 class Hash 的作用：
	//1. 实现哈希函数的可定制性
	//在哈希表等数据结构中，需要一个哈希函数将键（K 类型）映射到一个整数（通常是 size_t 类型），这个整数用于确定键值对在哈希表中的存储位置。class Hash 的主要作用就是提供一种机制，让用户可以自定义哈希函数。
	//2. 默认哈希函数
	//Hash 模板参数有一个默认值 HashFunc<K>，这意味着如果用户在使用这个模板类时没有显式指定 Hash 类型，那么将使用 HashFunc<K> 作为哈希函数。HashFunc<K> 是一个仿函数（函数对象），它重载了 opera

template<class K>
struct HashFunc
{
	size_t operator()(const K & key)
	{
		return (size_t)key;
	}
};

// 特化
	//还可以:模板的特化:对于string类型直接走这个特化,不会再走原模版构造
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;

		}
		return hash;
	}
};


//避免桶的哈希表与这个方式冲突:namespace封起来
namespace openaddress
{
	//状态：枚举：
	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};


	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;//默认状态为空
	};


	

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}


		bool Insert(const pair<K, V>& kv)
		{
			//整数除以整数不能得到浮点数，只能得到整数，我们需要将/两边的整数都转为double
			//插入的数据达到size大小的七成，就扩容
			//判断是否需要扩容以防止死循环找不到空闲的空间
			// //下面这个不用这么麻烦，可以转换成10倍小数的思想
			//if ((double)_n/(double)_tables.size() >=0.7)
			// 
			if (10 * _n / _tables.size() >= 7)
			{
				//！！！扩容不能直接resize:一般都是扩容之后直接拷贝下来到新的空间，直接扩容，空间变了，那么映射关系也变了。就不能实现hashi了
				//因为之前冲突的值，扩容之后可能不冲突了，就应该在新的位置，而不是之前的紧接着++的位置了
				//为了让之前的数据正确的与新的表融合，最好新创一个表

				//下面这种方法还得重新映射，
				//vector<HashData<K, V>> newTables(_tables.size() * 2);
				////遍历旧表，将所有数据映射到新表
				////再交换新表和旧表。
				//_tables.swap(newTables);
				//有更好的方法：遍历旧表有数据的位置，插入新表，再交换
				//交换后，当前哈希表的 _tables 向量就包含了扩容后的数据，而新哈希表 newHT 的 _tables 向量在函数结束后会被销毁。
				HashTable<K, V,Hash> newHT;
				newHT._tables.resize(_tables.size() * 2);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._state == EXIST) //如果表中有值,就把这个值按映射关系放到新表里
					{
						newHT.Insert(_tables[i]._kv);//复用，不需要重新写下面的逻辑了
					}
				}

				_tables.swap(newHT._tables);
			}

			Hash hs;

			size_t hashi = hs(kv.first) % _tables.size();//计算起始位置
			//查找：二分/一次
			while (_tables[hashi]._state == EXIST)//如果这个位置的状态是已存在，那么++向后查找
			{
				++hashi;//直到找到状态是已删除或者空的位置，再插入
				//注意一点：如果找到最后一个位置，还得往前绕回开始，从前面没找过的位置继续找。
				hashi %= _tables.size();//绕回
			}
			//跑完再插入值，修改状态
			//~~~~~~~~~~~~如果全满？有可能死循环出不来循环
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;

			return true;
		}

		//查找： 
		HashData<K, V>* Find(const K& key)//返回键值对的地址（表中下标访问）
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();//找对应的哈希值
			while (_tables[hashi]._state != EMPTY)//存在和删除都要继续找，直到找到空还没找到值
			{
				//是通过确定key是否相等来判断是否找到该值的,
				if (_tables[hashi]._state == EXIST
					&& _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}

				++hashi;
				hashi %= _tables.size();//绕回
			}
			return nullptr;

		}

		//删除
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			//找到之后
			if (ret == nullptr)//要删除的地方没有值：直接不让删除，返回false
			{
				return false;
			}
			else
			{
				ret->_state = DELETE;
				return true;
			}
		}



	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;//统计表中存储的数据个数：
	};



	//某个位置被删除了，那就修改状态为删除

	void TestHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 11,21,4,14,24,15,9 };
		for (auto e : a)
		{
			ht.Insert({ e,e });
		}
		ht.Insert({ 19,19 });

		cout << ht.Find(24) << endl;
		ht.Erase(4);
		cout << ht.Find(24) << endl;
		cout << ht.Find(4) << endl;
		//删4，再找4就找不到了



	}



	//struct StringHashFunc
	//{
	//	//字符转整型最好的做法:取s中的每个字符,再相加他们的ASCLL码值
	//	size_t operator()(const string& s)
	//	{
	//		size_t n = 0;//避免冲突还可以加一些特殊处理
	//		for (auto e : s)
	//		{
	//			n += e;//在进行加法运算时，C++ 会自动将 char 类型的 e 提升为 int 类型
	//		}
	//		return n;
	//	}
	//};


	//用哈希表实现一个字典:
	void TestHT2()
	{
		HashTable<string, string> ht;

		ht.Insert({ "sort","排序" });
		ht.Insert({ "left","左边" });
		//❌:编译报错:插入的类型是kv:字符不再是int/int不能按之前的逻辑哈希
		//需要定义一个函数模板hash:将字符型强制转化为size_t整型
		 //但是string不支持转为整型:咋整:单独设置stringhash的函数


	}


}
//开放定址表


//哈希桶的办法挂起来,不想像上面一样挨个挨个向后查找.
namespace hash_bucket
{
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next;

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			, _next(nullptr)
		{}
	};


	template<class K,class V, class Hash = HashFunc<K>>
	class HashTable//表
	{
		typedef HashNode<K, V> Node;//键值对设为节点
	public:
		HashTable()
		{
			_tables.resize(10, nullptr);
		}

		~HashTable()
		{
			// 依次把每个桶释放
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		bool Insert(const pair<K,V>& kv)
		{
			Hash hs;
			size_t hashi =hs(kv.first) % _tables.size();
			//负载因子==1扩容
			if (_n == _tables.size())
			{
				//HashTable<K, V> newHT;
				//newHT._tables.resize(_tables.size() * 2);
				//for (size_t i = 0; i < _tables.size(); i++)
				//{
				//	Node* cur = _tables[i];
				//	while(cur)
				//	{
				//		newHT.Insert(cur_kv);//复用，不需要重新写下面的逻辑了
				//		cur = cur->_next;
				//	}
				//}

				//_tables.swap(newHT._tables);

				
				vector<Node*> newtables(_tables.size()*2,nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					// 定义了一个指向 Node 类型的指针 cur，并将其初始化为第 i 个桶对应的链表的头指针。通过这个指针 cur，可以遍历该链表中的所有节点。
					while (cur)
					{
						//保存当前节点的下一个节点指针,用于待会调整位置后的节点头链接
						Node* next = cur->_next;
						//旧表中的节点,挪动新表重新映射的位置
						size_t hashi =hs( cur->_kv.first) % newtables.size();
						//头插到新表
						cur->_next = newtables[hashi];//原尾接新头
						newtables[hashi] = cur;//cur来到新位置

						cur = next;// cur->_next;
						//把cur变为之前的自己的下一个,以达到出循环继续遍历链表的目的
					}
					_tables[i] = nullptr;//清空原哈希表当前桶的链表
				}
				_tables.swap(newtables);


			}

			//头插
			//size_t hashi = kv.first % _tables.size();
			Node* newnode = new Node(kv); 
			newnode->_next = _tables[hashi];//z站在头上
			_tables[hashi] = newnode;//把头挤下去 
			++_n;

			return true;
		} 

		Node* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}

				cur = cur->_next;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:


		vector<Node*> _tables;//指针数组//表由vector容器内的节点组成
		size_t _n = 0;//存储个数
	};

	void TestHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 11,21,4,14,24,15,9,19,29,39 };
		for (auto e : a)
		{
			ht.Insert({ e,e });
		}

		ht.Insert({ -6, 6 });

		for (auto e : a)
		{
			ht.Erase(e);
		}
	}

	void TestHT2()
	{
		HashTable<string, string> ht;
		ht.Insert({ "sort", "排序" });
		ht.Insert({ "left", "左边" });
	}















}


























